package g

/*
 * @lc app=leetcode.cn id=704 lang=golang
 *
 * [704] 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
*/

// @lc code=start
func search(nums []int, target int) int {
	return search2(nums, target)
}

func search1(nums []int, target int) int {
	var left int
	right := len(nums) - 1
	for left <= right {
		mid := ((right - left) >> 1) + left
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return -1
}

func search2(nums []int, target int) int {
	return searchRecursion(nums, 0, len(nums)-1, target)
}

func searchRecursion(nums []int, left, right, target int) int {
	if left <= right {
		mid := ((right - left) >> 1) + left
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] {
			return searchRecursion(nums, mid+1, right, target)
		} else {
			return searchRecursion(nums, left, mid-1, target)
		}
	}
	return -1
}

// @lc code=end
